#include<iostream>
using namespace std;
const int maxn=32;
int n,value[maxn][maxn],root[maxn][maxn];//value->dp数组  root->记录根 

void prt(int a,int b){
	if(a>b) return;
	cout<<root[a][b]<<" ";//当前区间根 
	prt(a,root[a][b]-1);//左子树根 
	prt(root[a][b]+1,b);//右子树根 
}//前序遍历

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>value[i][i];//自己到自己 加分为自己 
		root[i][i]=i;//自己到自己 根为自己 
	}//初始化 
		
	for(int i=n;i>=1;i--)//区间起点 
	    for(int j=i+1;j<=n;j++)//区间终点 
	        for(int r=i;r<=j;r++){//子树根 
	        	if(r==i&&value[i][j]<value[i][i]+value[i+1][j]){
	        	    value[i][j]=value[i][i]+value[i+1][j];
	        	    root[i][j]=i;
	        	}//只有右子树 
	        	else if(r==j&&value[i][j]<value[i][j-1]+value[j][j]){
	        		value[i][j]=value[i][j-1]+value[j][j];
	        		root[i][j]=j;
	        	}//只有左子树 
	        	else if(value[i][j]<value[r][r]+value[i][r-1]*value[r+1][j]){
	        		value[i][j]=value[r][r]+value[i][r-1]*value[r+1][j];
	        		root[i][j]=r;
	        	}//有左右子树 
	        	    
	        }
	cout<<value[1][n]<<endl;
	prt(1,n);
}
/*#include <iostream>
#include <cstring>
using namespace std;

int n, input[35], f[35][35], root[35][35];

int dfs(int left, int right) {
	if (left > right) return 1;
	if (f[left][right] >= 0) return f[left][right];
	if (left == right) {
		root[left][right] = left;
		return f[left][right] = input[left];
	} else {
		for (int k = left; k <= right; k++) 
			if (dfs(left, k - 1) * dfs(k + 1, right) + input[k] > f[left][right]) {
				f[left][right] = dfs(left, k - 1) * dfs(k + 1, right) + input[k];
				root[left][right] = k;
			}
		return f[left][right];
	}
}

void print(int left, int right) {//前序遍历 
	if (left <= right) {
		cout << root[left][right] << " ";
		print(left, root[left][right] - 1);
		print(root[left][right] + 1, right);
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> input[i];
	memset(f, -1, sizeof(f));
	memset(root, -1, sizeof(root));
	cout << dfs(1, n) << endl;
	print(1, n);
	cout << endl;
	return 0;
}
*/